#include <list>
#include <vector>
#include <queue>
#include <algorithm>

#include "cover.h"

using std::list;
using std::vector;
using std::max_element;

/**
 * Greedy algorithm based on SET COVER
 * Modifies: matrix, cover, solutions
 *
 * @param   matrix  the 0,1 matrix represented as vector of vectors of int
 * @param   ncols   number of data columns representing lines,
 *		    not number of characters
 * @param   nrows   number of rows
 * @param   cover   int array of length ncols
 * @param   solutions	a storage container for solution row indices
 */
void greedy_sc (
	vector<vector<int> > &matrix,
	size_t nrows,
	size_t ncols,
	int *cover,
	list<int> &solutions
	)
{
    /**
     * Algorithm description
     *
     * while not finished covering
     *. count the number of 1's in each row (rowsums)
     *. find the row with the greatest rowsum 
     *. add that row to the solution set
     *. cover matrix with that row
     */

    int *rowsums = new int[nrows];	// for greediness counting

    /* initialize rowsums: count the 1's in each row */
    initialize_row_column_sums(matrix, rowsums, NULL);

    int * const endrow = rowsums + nrows;
    while ( !finished(cover, ncols) ) {
	/* find max row */
	int * maxrow = max_element(rowsums, endrow);

	int rowi = maxrow - rowsums;	    // get maxrow index
	solutions.push_back(rowi);	    // add maxrow to solution set
	// cover matrix with row rowi
	cover_with_row (matrix, rowi, cover, rowsums, NULL);
    }

    /* clean up duty -- free up memory */
    delete[] rowsums;
}

